package cn.lena.leecode.arr;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author lena
 * @date 2021/6/22
 * t
 */
public class Offer40 {


	/**
	 * 剑指offer40：最小的k个不重复的数
	 * @param arr
	 * @param k
	 * @return
	 */
	public int[] getLeastNumbers1(int[] arr, int k){
		if(arr.length ==0 || k == 0) {
			return new int[0];
		}
		quickSort(0,arr.length-1,arr);
		return Arrays.copyOf(arr,k);
	}
	void quickSort(int low,int high,int[] arr) {
		if(low>high) {
			return;
		}
		int i=low;
		int j=high;
		int sign=arr[low];
		while(i != j) {
			while(arr[j] >= sign && i<j) {
				j--;
			}
			if(j>i) {
				arr[i]=arr[j];
				i++;
			}
			while(arr[i] <= sign && i<j) {
				i++;
			}
			if(i<j) {
				arr[j]=arr[i];
				j--;
			}
		}
		arr[i]=sign;
		quickSort(low,i-1,arr);
		quickSort(i+1,high,arr);
	}

	/**
	 * 剑指offer40（扩）：最小k个不重复的数
	 * @param arr
	 * @param k
	 * @return
	 */
	public int[] getLeastNumbers2(int[] arr, int k) {
		if(arr.length ==0 || k == 0) {
			return new int[0];
		}
		TreeSet<Integer> ts=new TreeSet();
		for(int i=0; i<arr.length; i++) {
			ts.add(arr[i]);
		}
		int[] result=new int[k];
		int i=0;
		for(Integer current:ts) {
			if(i == k){
				break;
			}
			result[i++]=current;
		}
		return result;
	}


}
